package Hot_100;

import org.junit.Test;

import java.lang.ref.Reference;

public class T34_searchRange {
    @Test
    public void test() {
//        int nums[] = {1};
//        int nums[] = {2,2};
        int nums[] = {5,7,7,8,8,10};
        int[] ans = searchRange_2(nums, 8);
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i]+" ");
        }
    }


//    正确的解法是第一个target采用二分查找，最后一个target也是采用二分查找
    public int[] searchRange_2(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int first = binarySearchFirst(nums, target);
        if (first == -1) {
            return new int[]{-1, -1};
        }
        int last = binarySearchLast(nums, target);  //如果第一个target能找到，则最后一个target必定可以找到
        return new int[]{first, last};
    }


//  二分查找第一个元素
    public int binarySearchFirst(int []nums,int target) {
        int left,right,mid;
        left=0;
        right = nums.length-1;
        while (left < right) {
            mid = (left + right) >> 1;  //右移一位 即除2
            if (nums[mid] > target) {
                right=mid-1;
            } else if (nums[mid] == target) {
                right=mid;
            }else {
                left=mid+1;
            }
        }
        if (nums[left] != target) {
            return -1;
        }
        return left;
    }

    public int binarySearchLast(int []nums,int target) {
        int left,right,mid;
        left=0;
        right = nums.length-1;
        while (left < right) {
            mid = (left + right + 1) / 2;  //*************
            if (nums[mid] > target) {
                right=mid-1;
            } else if (nums[mid] == target) {
                left=mid;
                //当right=left+1,则mid=(left+right)/2=(left+left+1)/2=left,然后执行left=mid这个更新操作，相当于left没有变化，那么就会一直处在死循环里
                // 总结：如果出现left=mid这个更新操作，则mid的赋值应该写成mid=(left+right+1)/2
            }else {
                left=mid+1;
            }
        }
        return left;
    }


//    ----------------------------------------------------------------------
//    这是错误的写法，整个过程应该都是二分的;这里定位到target之后选择直接遍历的方式是错误的
    public int[] searchRange_1(int[] nums, int target) {

        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int start, mid, end;
        int indexFirst,indexLast;
        start=0;
        end=nums.length-1;
        mid=(start+end)/2;

        while (start < end) {

            if (nums[mid] == target) {        //判断是否相等
                break;
            }

            if (nums[mid] < target) {
                start=mid+1;
                if (start >= nums.length) {
                    return new int[]{-1, -1};
                }
            }else {
                end=mid-1;
                if (end < 0) {
                    return new int[]{-1, -1};
                }
            }
            mid=(start+end)/2;
        }

        if (start == end && nums[mid]!=target) {
            return new int[]{-1, -1};
        }

//        找target在数组的第一个值
        for (indexFirst = mid; indexFirst >= 0; ) {
            if (nums[indexFirst] == target) {
                indexFirst--;
            }else {
                break;
            }
        }
        indexFirst++;

//        找target在数组的最后一个值
        for (indexLast = mid; indexLast <nums.length ; ) {
            if (nums[indexLast] == target) {
                indexLast++;
            }else {
                break;
            }
        }
        indexLast--;

        return new int[] {indexFirst, indexLast};
    }
}
